package algorithm7.leetcode.hot100.c2双指针;

import org.junit.jupiter.api.Test;

public class h7_LC42接雨水 {

/*
https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
42. 接雨水
困难
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

 */

    class Solution {
        public int trap(int[] height) {
//            return handle1_plus(height);
            return handle2(height);
        }

        /*
            双指针解法
            初始化l,r左右指针，l_max,r_max记录左边最大高度和右边最大高度
            l向右移动，循环条件 l < r
                如果height[l]小于height[r]，在左侧寻找低洼处，①如果height[l]大于l_max，不能形成低洼无法接到雨水，l++；②height[l]小于l_max，此处雨水为 l_max - height[l]
                如果height[l]大于height[r]，在右侧寻找低洼处，①如果height[r]大于r_max，不能形成低洼无法接到雨水，r--；②height[r]小于r_max，此处雨水为 r_max - height[r]
         */
        private int handle1(int[] height) {
            int l = 0, r = height.length - 1;
            int l_max = 0, r_max = 0;
            int ans = 0;
            while (l < r) {
                if (height[l] < height[r]) {
                    if (height[l] >= l_max) {
                        l_max = height[l];
                    } else {
                        ans += l_max - height[l];
                    }
                    l++;
                } else {
                    if (height[r] >= r_max) {
                        r_max = height[r];
                    } else {
                        ans += r_max - height[r];
                    }
                    r--;
                }
            }
            return ans;
        }
        // 双指针改良，减少if分支
        private int handle1_plus(int[] height) {
            int l = 0, r = height.length - 1;
            int l_max = height[l], r_max = height[r];
            int ans = 0;
            while (l < r) {
                if (height[l] < height[r]) {
                    ans += l_max - height[l];
                    l_max = Math.max(l_max, height[++l]);
                } else {
                    ans += r_max - height[r];
                    r_max = Math.max(r_max, height[--r]);
                }
            }
            return ans;
        }
    }

    /*
        动态规划解法
        对于位置i有，i位置能接到的水=min(i位置左边最高高度l_max，i位置右边最高高度r_max) - i位置高度
        先初始化l_max,r_max两个数组【dp】，就能避免每次在i位置去遍历找l_max,r_max
     */
    private int handle2(int[] height) {
        int ans = 0, n = height.length;
        int[] l_max = new int[height.length];
        int[] r_max = new int[height.length];
        l_max[0] = height[0];
        for (int i = 1; i < n; i++) {
            l_max[i] = Math.max(l_max[i - 1], height[i]);
        }
        r_max[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            r_max[i] = Math.max(r_max[i + 1], height[i]);
        }
        for (int i = 0; i < n; i++) {
            ans += Math.min(l_max[i], r_max[i]) - height[i];
        }
        return ans;
    }

    @Test
    void test() {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int ans = new Solution().trap(height);
        System.out.println("ans = " + ans);
    }

}
